/*
题目: 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

https://leetcode.cn/problems/surrounded-regions
 */
public class Solve {
    char[][] visited = null;
    int row, col;
    int[][] dir = new int[][] {{1,0},{-1,0},{0,-1},{0,1}};

    public void solve(char[][] board) {
        // 核心思路: 找到没有被环绕的地方
        row = board.length;
        col = board[0].length;

        // 再遍历 4 条边
        for (int i = 0; i < col; i++) {
            if (board[0][i] == 'O') {
                dfs(board, 0, i);
            }
            if (board[row - 1][i] == 'O') {
                dfs(board, row - 1, i);
            }
        }

        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][col - 1] == 'O') {
                dfs(board, i, col - 1);
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] != 'J') {
                    board[i][j] = 'X';
                } else {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int x, int y) {
        board[x][y] = 'J';

        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
                continue ;
            }
            // 没有访问过, 并且是 'O'
            if (board[nextX][nextY] == 'O') {
                dfs(board, nextX, nextY);
            }
        }
    }
}
